#include <vector>

using namespace std;


/**
 * @brief 74. 搜索二维矩阵
 * https://leetcode.cn/problems/search-a-2d-matrix/
 * [二分查找]
 */
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int l = 0;
        int r = m * n - 1;

        while (l <= r) {
            int mid = (l + r) / 2;
            int row = mid / n;
            int col = mid - row * n;
            if (matrix[row][col] < target) l = mid+1;
            else if (matrix[row][col] > target) r = mid-1;
            else return true;
        }

        return false;
    }
};
